#include <iostream>
#include <vector>
#include <functional>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

class Solution
{
public:
    vector<vector<int>> colorBorder(vector<vector<int>> &grid, int row, int col, int color)
    {
        int n = grid.size(), m = grid[0].size();
        auto res = grid;
        int directions[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int c = grid[row][col];
        vector<vector<bool>> f(n, vector<bool>(m, false));

        function<void(int, int)> dfs = [&](int x, int y)
        {
            bool ok = false;
            for (int i = 0; i < 4; i++)
            {
                int nx = x + directions[i][0];
                int ny = y + directions[i][1];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && !f[nx][ny])
                {
                    if (grid[nx][ny] == c)
                    {
                        f[nx][ny] = true;
                        dfs(nx, ny);
                    }
                    else
                    {
                        ok = true;
                    }
                }
                if (ok || !x || !y || x == n - 1 || y == m - 1)
                    res[x][y] = color;
            }
        };
        dfs(row, col);
        return res;
    }
};